from model import *
from datetime import datetime
from util import *
from scoring import *
from heapq import nlargest, nsmallest
from itertools import tee, chain
import re

#TODO:
# 1. change posting.getDocIDs() to a generator to save memory.

DEFAULT_RESULT_LIMIT = 50000

class QueryManager:
    '''Parses queries and returns result.'''
    
    def __init__(self, index):
        '''Constructor for QueryManager.
        @param collection: Collection instance to run queries against.'''
        self.index = index
        self.qp = QueryParser()
        
    def handle(self, input, limit=DEFAULT_RESULT_LIMIT, ranked=False, advanced=None):
        '''Handles raw user input.
        @param input: raw user input.'''
        if not advanced:
            query = self.qp.parse(input)
            results = query.execute(self.index).limit(limit)
            if not ranked:
                results.display()
            else:
                scorer = query.scorer(self.index, advanced)
                results.orderWith(scorer).display()
        else:
            query = self.qp.advancedparse(input)                # query is an instance of QuerySequence
            if query.isA(QuerySequence):
                # results is ranked by default
                results = query.execute(self.index, advanced).limit(limit)
                results.detaildisplay(self.index)
            else:
                results = query.execute(self.index).limit(limit)
                if not ranked:
                    results.detaildisplay(self.index)
                else:
                    scorer = query.scorer(self.index, advanced)
                    results.orderWith(scorer).detaildisplay(self.index)
                    #fltr = Filter(self.index.labmnb, results.orderWith(scorer).top(1)[0])
                    #results.orderWith(scorer).filterBy(fltr).detaildisplay(self.index)
        return query

    def display(self, results):
        '''Prints results in a certain fashion.'''
        print ','.join(map(str,results))

    
class QueryParser:
    '''Parses queries.'''
    def __init__(self):
        pass
    
    def parse(self, input):
        string = re.sub('\s+',' ',re.sub('[^A-Za-z\s\(\)\"\*]',' ',input)).strip()
        if not string:
            return NullQuery()
        if containOp(string):
            return BooleanQuery.create(string)
        else:
            if ' ' in string:
                if '"' in string:
                    return Phrase.create(string)
                else:
                    return Term.create(string)
            else:
                return Term.create(string)

    def advancedparse(self, input):
        string = re.sub('\s+',' ',re.sub('[^A-Za-z\s\(\)\"\*]',' ',input)).strip()
        if not string:
            return NullQuery()
        if containOp(string):
            return BooleanQuery.create(string)
        else:
            if ' ' in string:
                if '"' in string:
                    return Phrase.create(string)
                else:
                    return QuerySequence(Phrase.create(string),
                                         BooleanQuery.create(' AND '.join(filter(lambda x:x.lower() not in STOPWORDS, string.split(' ')))),
                                         Term.create(string))
            else:
                return Term.create(string)

class Filter:
    def __init__(self, classes, top1docid):
        self.classes = classes
        self.targetclass = classes[top1docid]

    def filter(self, docid):
        return set(self.classes[docid]) & set(self.targetclass) != set([])

    
class Result:
    ''' Represents a search result.
    Usage:
    >> query = qm.qp.parse('test')
    >> result = query.execute(index)
    >> result.display()
    "1,6,8,10,..."
    >> result.all()
    [1,6,8,10,...]
    >> result[1]
    6
    >> result.limit(3).display()
    "1,6,8"
    >> len(result)
    159
    >> result.count
    159
    >> result = result.limit(3)
    >> len(result)
    159
    >> result.count
    3
    >> scorer = Cosine(xxx,xxx)
    >> result.orderWith(scorer).display()
    "57,8,109,6,1, ...."
    >> another_result = Result(result)
    >> another_result.display()
    "1,6,8"
    '''
    
    def __init__(self, docs=[], limit=None, scorer=None, runtime=0):
        '''
        @param docs: IMPORTANT: docs can be any iterable(list, set, tuple, you name it) or generator.
        @param limit: max. number of results. 5000 by default.
        @param scorer: scorer.
        @param runtime: the total runtime of this query. currently unused. need to think of some way to reflect the real execution time.
        '''
        self.docs, self.original = tee(docs)
        self.lmt = limit
        self.scorer = scorer
        self.runtime = runtime

    def reset(self):
        if type(self.original) == list:
            return
        self.docs, self.original = tee(self.original)

    def __len__(self):
        ''' The total length of all the results before ranking and limiting. '''
        self.docs = self.original = list(self.original)
        self.length = len(self.docs)
        return self.length
    
    def __iter__(self):
        ''' Yields the results one by one like a generator. '''
        self.reset()
        if self.scorer is None:
            if self.lmt is None:
                for i in self.docs:
                    yield i
            else:
                i = 0
                for i in self.docs:
                    if i < self.lmt:
                        yield i
                        i += 1
        else:
            scr = self.scorer.score
            if self.lmt is None:
                for i in sorted(self.docs, key=scr, reverse=True):
                    yield i
            else:
                for i in nlargest(self.lmt, self.docs, scr):
                    yield i

    def __getitem__(self, n):
        ''' Implemented to enable result[n] operation. '''
        self.docs = self.original = list(self.original)
        return self.docs[n]

    @property
    def count(self):
        ''' Actual result length. '''
        if self.lmt is None:
            return len(self)
        else:
            return min([len(self), self.lmt])

    def all(self):
        ''' Returns the results in a list. '''
        self.reset()
        # no ranking
        if self.scorer is None:
            if self.lmt is None:
                return list(self.docs)
            else:
                result = []
                i = 0
                for docid in self.docs:
                    if i < self.lmt:
                        result.append(docid)
                        i += 1
                return result
        else:
            scr = self.scorer.score
            if self.lmt is None:
                return sorted(self.docs, key=scr, reverse=True)
            else:
                return nlargest(self.lmt, self.docs, scr)

    def top(self, n):
        self.reset()
        if self.scorer is None:
            return nsmallest(n, self.docs)
        else:
            scr = self.scorer.score
            return nlargest(n, self.docs, scr)

    def display(self):
        print ','.join(map(str,self))

    def detaildisplay(self, index):
        i = 0
        for r in self:
            print '%d %d %s'%(i, r, index.titles[r])
            i += 1
        print

    def limit(self, limit):
        self.lmt = limit
        return self

    def orderWith(self, scorer):
        self.scorer = scorer
        return self

    def filterBy(self, fltr):
        self.reset()
        self.docs, self.original = tee(filter(lambda x: fltr.filter(x), list(self.docs)))
        return self

class ResultSequence():
    def __init__(self, *results):
        self.results = results
        self.numofresults = len(results)
        self.lmt = DEFAULT_RESULT_LIMIT

    def __iter__(self):
        n = 0
        if self.numofresults == 0:
            return
        yielded = set()
        for docid in self.results[0]:
            if n < self.lmt:
                yield docid
                yielded.add(docid)
                n += 1
            else:
                return
        if self.numofresults > 1:
            for r in self.results[1:]:
                for docid in r:
                    if n < self.lmt:
                        if docid not in yielded:
                            yield docid
                            yielded.add(docid)
                            n += 1
                        else:
                            continue
                    else:
                        return

    def limit(self, limit):
        self.lmt = limit
        return self                    

    def display(self):
        print ','.join(map(str,self))

    def detaildisplay(self, index):
        i = 0
        for r in self:
            print '%d %d %s'%(i, r, index.titles[r])
            i += 1
        print

class Query:
    '''Abstract base class for query objects.'''
    runtime = 0

    @classmethod
    def create(self):
        '''Virtual function. If we think something protentially belongs to some sub-class of Query's,
        we call sub-class.create() instead of the sub-class's constructor. The reason is that it could
        turned out to belong to another sub-class, e.g., Term.create('and') is actually a NullQuery
        because 'and' is in the STOPWORDS. Constructors are only called when we are sure that something
        belongs to this class. This function provides preprocess and optimization upon query creation.
        Imagine a Boolean query, with 100 keywords all connected by AND, and the last one actually does
        not return anything. With this function we can determine this situation at the beginning and
        avoid heavy computing.
        @return: An instance of a subclass.'''
        raise NotImplementedError

    def isA(self, cls):
        '''Determine whether an instance is of some class.
        @param cls: class name to inspect.'''
        return isinstance(self, cls)
    
    def execute(self, index):
        '''Returns a Result instance. Wrapper of the _execute function. '''
        raise NotImplementedError

    def _execute(self, index):
        '''Generator. Virtual function. Executes self and yields results one by one.
        @param index: index to search query in.'''
        raise NotImplementedError

    def termIDs(self, index):
        raise NotImplementedError

    def scorer(self, index, advanced=False):
        raise NotImplementedError

class QuerySequence(Query):
    def __init__(self, *queries):
        self.queries = queries

    def execute(self, index, advanced=False):
        return ResultSequence(*[q.execute(index).orderWith(q.scorer(index, advanced)) for q in self.queries])

class NullQuery(Query):
    '''Queries that does not generate any result.'''
    def execute(self, index):
        return Result()

    def _execute(self, index):
        if False:
            yield -1
    
    def __repr__(self):
        return 'NullQuery()'

    def __str__(self):
        return 'Null'

    def termIDs(self, index):
        return []

    def scorer(self, index, advanced=False):
        return None

class Term(Query):
    '''Basic unit of a query. Every word other than operators is a Term instance, if not a NullQuery.'''
    term = ''
    original = ''
    
    def __init__(self, term, original=''):
        self.term = term
        self.original = original
        self.termid = None
        
    def __repr__(self):
        return 'Term(%s)'%self.term
    
    def __str__(self):
        return self.original
    
    @classmethod
    def create(cls, term):
        '''Several cases falls into this function:
        1. Single word queries
        2. Free text queries
        3. Single wild card queries
        4. Free text queries with wildcard terms'''
        # filter out illegal characters
        kws = []
        for tt in term.lower().split(' '):
            t = re.sub('[^A-Za-z\*]','',tt)
            if not t: continue
            if '*' in t:
                kws.append(WildcardTerm.create(t))
            else:
                st = stem(t, 0)
                if st not in STOPWORDS:
                    kws.append(cls(st, t))
                else:
                    kws.append(NullQuery())
        if len(kws)==1:
            return kws[0]
        else:
            temp = Or(kws[0], kws[1])
            for t in kws[2:]:
                temp = Or(temp,t)
            return temp

    # One word query
    def execute(self, index):
        ''' Wrapper function. Break the old execute function into 2 parts
        so that the inner function can still perform like a generator, and
        the outer wrapper can construct a Result instance using a generator
        other than a big list. Memory efficient.
        '''
        return Result(docs=self._execute(index))
    
    def _execute(self, index):
        '''Generator. Outputs a set of document IDs that answer one word query
        @param index: index of dictionary and postings
        @return: a list of document IDs, or an empty list if input word does not exist.'''
        p = index.byTerm(self.term)
        if p:
            self.termid = p.id
            for i in p.getDocIDs():
                yield i

    def termIDs(self, index):
        if self.termid:
            return [self.termid]
        else:
            p = index.byTerm(self.term)
            if p:
                return [p.id]
            else:
                return []

    def scorer(self, index, advanced=False):
        tids = self.termIDs(index)
        if tids:
            if advanced:
                #return BM25(index, tids)
                #return PageRankScorer(index, tids)
                top1 = self.execute(index).top(1)
                if not top1: return None
                if advanced == '-svm':
                    return SVMScorer(index, tids, top1[0])
                elif advanced == '-mnb':
                    return MNBScorer(index, tids, top1[0])
            else:
                return Cosine(index, tids)
        else:
            return None
        
class WildcardTerm(Query):
    '''Handles wildcard terms. '''
    def __init__(self, term):
        self.term = term
        self.termdict = {}

    def __repr__(self):
        return 'Wildcard(%s)'%self.term

    def __str__(self):
        return self.term        
        
    @classmethod
    def create(cls, term):
        '''We are dealing with several kinds of wildcard terms here:
        1. red*
        2. *red
        3. ap*le
        4. ap*l*
        5. etc
        First, prefix needs to be extracted for each kind. For those who has more than 1 stars,
        extract the substring before the first star, and later filter out false results.
        '''
        return cls(term)

    def execute(self, index):
        return Result(docs=self._execute(index))
        docs = list(self._execute(index))
        return Result(docs=docs)

    def _execute(self, index):
        ''' Look for matching terms first, then build an Or instance and executes it.
        '''
        terms = self.getterms(index)
        if not terms:
            return
        lt = len(terms)
        if lt == 1:
            p = index.byTerm(stem(terms[0],0))
            if p:
                for i in p.getDocIDsForTokens(terms):
                    yield i
        else:
            for docid in sorted(set(chain(*[p.getDocIDsForTokens(terms) for p in filter(lambda x:x, [index.byTerm(stem(t,0)) for t in terms])]))):
                yield docid

    def getterms(self, index):
        if not self.termdict:
            terms = list(index.dictionary.lookup(self.term))
            tmdict = index.dictionary.termdict
            for t in terms:
                self.termdict[t] = tmdict.get(stem(t,0),-1)
        return self.termdict.keys()

    def termIDs(self, index):
        if not self.termdict:
            terms = list(index.dictionary.lookup(self.term))
            tmdict = index.dictionary.termdict
            for t in terms:
                self.termdict[t] = tmdict.get(stem(t,0),-1)
        return filter(lambda x:x!=-1, list(set(self.termdict.values())))

    def scorer(self, index, advanced=False):
        tids = self.termIDs(index)
        if tids:
            if advanced:
                distances = {}
                for k,v in self.termdict.items():
                    distances[v] = distance(self.term, k)
                return LevenshteinCosine(index, tids, distances)
            else:
                return Cosine(index, tids)
        else:
            return None


class Phrase(Query):
    '''Class for ["xxx yyy"] type queries'''
    terms = []
    original = ''
    
    def __init__(self, terms, original=''):
        self.terms = terms
        self.original = original
        self.termids = []
        self.docs = []

    def __repr__(self):
        return 'Phrase(%s)'%(','.join([repr(t) for t in self.terms]))

    def __str__(self):
        return self.original
        
    @classmethod
    def create(cls, terms):
        '''@param term: pretty much the original search string, e.g., "square root".'''
        ret = []
        for term in terms.lower().split(' '):
            if term in STOPWORDS:
                continue
            t = Term.create(term)
            if t.isA(NullQuery):
                return NullQuery()
            else:
                ret.append(t)
        if ret:
            if len(ret) > 1:
                return cls(ret, terms)
            else:
                return ret[0]
        else:
            return NullQuery()

    def termIDs(self, index):
        if not self.termids:
            postings = filter(lambda x: x, [index.byTerm(t.term) for t in self.terms])
            self.termids = [p.id for p in postings]
        return self.termids
    
    def scorer(self, index, advanced=False):
        if advanced:
            #return CompondScorer(index, [BM25(index, tid) for tid in self.termIDs(index)])
            #return CompondScorer(index, [PageRankScorer(index, tid) for tid in self.termIDs(index)])
            top1 = self.execute(index).top(1)
            if top1:
                if advanced == '-svm':
                    return CompondScorer(index, [SVMScorer(index, tid, top1[0]) for tid in self.termIDs(index)])
                elif advanced == '-mnb':
                    return CompondScorer(index, [MNBScorer(index, tid, top1[0]) for tid in self.termIDs(index)])
            else:
                return None
        else:
            return CompondScorer(index, [Cosine(index, tid) for tid in self.termIDs(index)])
        
    # Phrase Query
    def execute(self, index):
        return Result(self._execute(index))
    
    def _execute(self, index):
        '''Generator. Output a set of document IDs that answer phrase query. This method can handle
        more than two words phrase query
        @param index: index of dictionary and postings
        @return: a list of document IDs'''
        
        bq = And(self.terms[0],self.terms[1])
        if len(self.terms)>2:
            for t in self.terms[2:]: # xrange(2,len(terms)):
                bq = And(bq,t)
        docs = bq._execute(index)
        if not docs: return
        if filter(lambda x: not x.isA(Term), self.terms):
            return
        else:
            postings = filter(lambda x: x, [index.byTerm(t.term) for t in self.terms])
            self.termids = [p.id for p in postings]
            termnum = len(postings)
            if termnum < len(self.terms):
                return
            for d in docs:
                idxs = [0 for i in xrange(termnum)]
                pls = [p[d] for p in postings]
                skips = [p.skip[d] if d in p.skip else {} for p in postings]
                while 1:
                    if isAdjacent(pls, idxs):
                        yield d
                        break   #only 1 occurance is found and then advance to next docid.
                    terminate = 0
                    for i in xrange(termnum):
                        if i < termnum-1 and pls[i][idxs[i]] < pls[i+1][idxs[i+1]]-1:
                            if skips[i].has_key(idxs[i]) and pls[i][skips[i][idxs[i]]] <= pls[i+1][idxs[i+1]]-1:
                                while skips[i].has_key(idxs[i]) and pls[i][skips[i][idxs[i]]] <= pls[i+1][idxs[i+1]]-1:
                                    idxs[i] = skips[i][idxs[i]]
                            else:
                                if idxs[i] < len(pls[i])-1:
                                    idxs[i] += 1
                                else:
                                    terminate = 1
                                    break
                        elif i > 0 and pls[i][idxs[i]] < pls[i-1][idxs[i-1]]+1:
                            if skips[i].has_key(idxs[i]) and pls[i][skips[i][idxs[i]]] <= pls[i-1][idxs[i-1]]+1:
                                while skips[i].has_key(idxs[i]) and pls[i][skips[i][idxs[i]]] <= pls[i-1][idxs[i-1]]+1:
                                    idxs[i] = skips[i][idxs[i]]
                            else:
                                if idxs[i] < len(pls[i])-1:
                                    idxs[i] += 1
                                else:
                                    terminate = 1
                                    break
                    if terminate: break

class BooleanQuery(Query):
    '''Abstract class for Boolean Queries.'''

    @classmethod
    def create(cls, line):
        '''Parse the infix query into a postfix deque and evaluate it.
        @return: An instance of one of [NullQuery, Term, And, AndNot, Or, Not]'''
        postfix = infix2postfix(line)
        operand = deque()
        for i in postfix:
            if i == 'AND':
                opd1 = operand.pop()
                opd2 = operand.pop()
                if not opd1 or not opd2:
                    operand.append(NullQuery())
                else:
                    operand.append(And.create(opd1, opd2))
            elif i == 'OR':
                opd1 = operand.pop()
                opd2 = operand.pop()
                if not opd1:
                    operand.append(opd2)
                elif not opd2:
                    operand.append(opd1)
                else:
                    operand.append(Or.create(opd1, opd2))
            elif i == 'NOT':
                opd = operand.pop()
                if not opd:
                    # a single NOT without an operand, ignore
                    operand.append(NullQuery())
                else:
                    operand.append(Not.create(opd))
            else:
                operand.append(Term.create(i))
        return operand[0]
                        
class And(BooleanQuery):
    '''Class for [x AND y] type queries'''
    
    def __init__(self, op1, op2):
        self.op1, self.op2 = op1, op2
        self.termids = []
    def __repr__(self):
        return 'And(%s,%s)'%(repr(self.op1), repr(self.op2))
    def __str__(self):
        pattern = [int(self.op1.isA(Term)), int(self.op2.isA(Term))]
        patternstr = ['(%s)','%s']
        return (patternstr[pattern[0]] + ' AND ' + patternstr[pattern[1]])%(str(self.op1), str(self.op2))

    def termIDs(self, index):
        if not self.termids:
            self.termids.extend(self.op1.termIDs(index))
            self.termids.extend(self.op2.termIDs(index))
        return self.termids
    
    def scorer(self, index, advanced=False):
        return CompondScorer(index, [self.op1.scorer(index, advanced), self.op2.scorer(index, advanced)])
    
    @classmethod
    def create(self, op1, op2):
        '''@return: An instance of one of [NullQuery, And, AndNot, Not(Or)]'''
        if op1.isA(NullQuery) or op2.isA(NullQuery):
            return NullQuery()
        else:
            if op1.isA(Not) and op2.isA(Not):
                return Not.create(Or.create(op1.op, op2.op))
            elif op1.isA(Not):
                return AndNot.create(op2, op1.op)
            elif op2.isA(Not):
                return AndNot.create(op1, op2.op)
            else:
                return And(op1,op2)

    def execute(self, index):
        return Result(self._execute(index))    
    
    def _execute(self, index):
        '''Depending on the class of op1 and op2, use different stratigies. Use skip pointers whenever available.'''
        if self.op1.isA(Term) and self.op2.isA(Term):
            p1 = index.byTerm(self.op1.term)
            p2 = index.byTerm(self.op2.term)
            if p1 and p2:
                doc1 = p1.getDocIDs()
                doc2 = p2.getDocIDs()
                if not doc1 or not doc2:
                    return
                idx1,idx2 = 0,0
                while idx1 < p1.docnum and idx2 < p2.docnum:
                    if doc1[idx1] == doc2[idx2]:
                        yield doc1[idx1]
                        idx1 += 1
                        idx2 += 1               
                    elif doc1[idx1] < doc2[idx2]:
                        if p1.docskip.has_key(idx1) and doc1[p1.docskip[idx1]] <= doc2[idx2]:
                            while p1.docskip.has_key(idx1) and doc1[p1.docskip[idx1]] <= doc2[idx2]:
                                idx1 = p1.docskip[idx1]
                        else:
                            idx1 += 1
                    else:
                        if p2.docskip.has_key(idx2) and doc2[p2.docskip[idx2]] <= doc1[idx1]:
                            while p2.docskip.has_key(idx2) and doc2[p2.docskip[idx2]] <= doc1[idx1]:
                                idx2 = p2.docskip[idx2]
                        else:
                            idx2 += 1
            else:
                return
        elif self.op1.isA(Term) or self.op2.isA(Term):
            if self.op1.isA(Term):
                p = index.byTerm(self.op1.term)
                doc2 = self.op2._execute(index)
            else:
                p = index.byTerm(self.op2.term)
                doc2 = self.op1._execute(index)
            if p:
                doc1 = p.getDocIDs()
                idx = 0
                try:
                    d = doc2.next()
                except:
                    return
                while idx < p.docnum:
                    if doc1[idx] == d:
                        yield d
                        idx += 1
                        try:
                            d = doc2.next()
                        except:
                            return
                    elif doc1[idx] < d:
                        if p.docskip.has_key(idx) and doc1[p.docskip[idx]] <= d:
                            while p.docskip.has_key(idx) and doc1[p.docskip[idx]] <= d:
                                idx = p.docskip[idx]
                        else:
                            idx += 1
                    else:
                        try:
                            d = doc2.next()
                        except:
                            return
            else:
                return            
        else:   # Neither is a Term
            for i in sorted(set(self.op1._execute(index)) & set(self.op2._execute(index))):
                yield i
            

class AndNot(Query):
    '''Class for [x AND NOT y] type queries'''
    def __init__(self, op1, op2):
        self.op1, self.op2 = op1, op2
        self.termids = []
    def __repr__(self):
        return 'AndNot(%s,%s)'%(repr(self.op1), repr(self.op2))
    def __str__(self):
        return ("%s AND NOT %s" if self.op2.isA(Term) else "%s AND NOT (%s)")%(str(self.op1), str(self.op2))
    
    def termIDs(self, index):
        if not self.termids:
            self.termids.extend(self.op1.termIDs(index))
            self.termids.extend(self.op2.termIDs(index))
        return self.termids

    def scorer(self, index, advanced=False):
        return CompondScorer(index, [self.op1.scorer(index, advanced), self.op2.scorer(index, advanced)])
    
    @classmethod
    def create(self, op1, op2):
        '''@return: An instance of one of [NullQuery, AndNot], or op1'''
        if op1.isA(NullQuery):  # cannot possibly happen because Add.create has already filtered out NullQueries. Provided anyways.
            return NullQuery()
        elif op2.isA(NullQuery):
            return op1
        else:
            return AndNot(op1, op2)

    def execute(self, index):
        return Result(self._execute(index))

    def _execute(self, index):
        for i in sorted(set(self.op1._execute(index)) - set(self.op2._execute(index))):
            yield i

class Or(Query):
    '''Class for [x OR y] type queries'''
    def __init__(self, op1, op2):
        self.ops = [op1, op2]
        self.simplify()
        self.termids = []
    def __repr__(self):
        return 'Or(%s)'%','.join(map(repr, self.ops))
        #return 'Or(%s,%s)'%(repr(self.op1), repr(self.op2))
    def __str__(self):
        return ' OR '.join(map(str, self.ops))
        #return "%s OR %s"%(str(self.op1), str(self.op2))
    
    @classmethod
    def create(self, op1, op2):
        '''@return: An instance of one of [NullQuery, Or], or op1, or op2'''
        if op1.isA(NullQuery) and op2.isA(NullQuery):
            return NullQuery()
        elif op1.isA(NullQuery):
            return op2
        elif op2.isA(NullQuery):
            return op1
        else:
            return Or(op1,op2)

    def simplify(self):
        temp = []
        for o in self.ops:
            if o.isA(Or):
                o.simplify()
                temp.extend(o.ops)
            else:
                temp.append(o)
        self.ops = temp
        
    def termIDs(self, index):
        if not self.termids:
            for o in self.ops:
                self.termids.extend(o.termIDs(index))
        return self.termids

    def scorer(self, index, advanced=False):
        return CompondScorer(index, filter(lambda x: x, [o.scorer(index, advanced) for o in self.ops]))
        
    def execute(self, index):
        return Result(self._execute(index))

    def _execute(self, index):
        for i in sorted(set(chain(*[o._execute(index) for o in self.ops]))):
            yield i
        
class Not(Query):
    '''Class for [NOT x] type queries'''
    def __init__(self, op):
        self.op = op
    def __repr__(self):
        return 'Not(%s)'%(repr(self.op))
    def __str__(self):
        return ("NOT %s" if self.op.isA(Term) else 'NOT (%s)')%(str(self.op))

    def termIDs(self, index):
        return self.op.termIDs(index)
    
    def scorer(self, index, advanced=False):
        return self.op.scorer(index, advanced)

    @classmethod
    def create(self, op):
        if op.isA(NullQuery):
            return NullQuery()
        else:
            return Not(op)

    def execute(self, index):
        return Result(self._execute(index))

    def _execute(self, index):
        for i in sorted(set(xrange(index.docnum)) - set(self.op._execute(index))):
            yield i

   
    

        